package ga;


//import java.util.Random;
import ewe.util.Random;

/**
 * MasterMindBase, contiene:              
 * 				<br>** La representacion de los colores
 *				<br>** Longitud de la combinacion
 *				<br>** Historia de jugadas
 *				<br>** Numero de intentos antes de perder
 *				<br>** Cantidad de poblacion
 *				<br>** Porcentaje de mutacion (crossover, mutacion circular, transposicion)
 *				<br>** Calificacion de una jugada con respecto al codigo secreto
 *				<br>** Crear combinacion aleatoria 	
 * @author Roberto Loaeza Valerio
 *
 */
public class MasterMindBase {
	/**
	 * Nombre de colores
	 */
	char colores[] = {'0', '1', '2', '3', '4', '5', '6', '7'};
	/**
	 * Codigo Secreto
	 */
	private char[] codigo;
	
	/**
	 * Cantidad de colores disponibles
	 */
	private int N = 8;
	/**
	 * Caracteres adicionales al codigo: D, W, B.
	 */
	private int cAux = 3;
	/**
	 * Longitud de combinacion
	 */
	public static int L = 5;
	/**
	 * Cantidad de poblacion
	 */
	public int nPob = 400;
	
	/**
	 * Maximo numero de jugadas
	 */
	public int J = 10;	
	/**
	 * Numero de generaciones sin tener una combinacion consistente antes de hacer Hipermutacion
	 */
	public int nH = 15;
	/**
	 * Porcentaje de cruza
	 */
	public int nC =40;
	/**
	 * Porcentaje de transposicion
	 */
	public int nT = 20;
	/**
	 * Porcentaje de mutacion circular
	 */
	public int nM =40;
	/**
	 * Numero maximo de hipermutaciones
	 */
	public int nR = 200;		
	/**
	 * Jugadas Realizadas
	 */
	public int nJ=0;
	/**
	 * Historia de jugadas realizadas
	 */
	public char[][] historia;
	/**
	 * Poblacion
	 */
	private static char[][] poblacion;
	/**
	 * Aleatorio
	 */
	public Random r = new Random();
	
	
	/**
	 * Crea una combinacion
	 * @return Nueva combinacion
	 */
	private char[] crearCombinacion() {
		char[] ret = new char[L+cAux];
		for(int i=0; i<(L+cAux); i++)
			ret[i]=i<L?colores[r.nextInt(N)]:ret[0];
		
		return ret;
	}
	
	/**
	 * Es contenido un caracter C en un arreglo S, entre la posicion 0 y N
	 * @param c Caracter
	 * @param S Arreglo de caracteres
	 * @param n Ultima posicion a buscar 
	 * @return True si C es contenido en S, en caso contrario False
	 */
	public boolean contiene(char c, char[] S, int n) {
		int i=0;
		while(i<=n)
			if(c==S[i++])
				return true;
		return false;
	}
	/**
	 * Crea una combinacion sin colores repetidos
	 * @return Combinacion sin colores repetidos
	 */
	public  char[] crearCombinacionUniq(){	 
       char[] ret = new char[L+cAux];
       int i=0;
       while(i<L) {
    	   ret[i]=colores[r.nextInt(N)];
    	   i+=existeEn(ret, ret[i], i)?0:1;
       }
       ret[i++]=ret[0];
       ret[i++]=ret[0];
       ret[i++]=ret[0];
       return ret;	       
    }
								
	/**
	 * Obtiene la distancia entre la jugada y el codigo secreto
	 * @param i indice de la combinacion
	 * @return distancia entre la jugada y el codigo secreto
	 */
	private int getFitness(int i) {
		return poblacion[i][L+0]-48;
	}
	/**
	 * Obtiene la cantidad de blancas (color existente pero fuera de su lugar)
	 * @param c Combinacion
	 * @return Cantidad de blancas
	 */
	public int getW(char[] c) {		
		return c[L+1]-48;
	}
	/**
	 * Obtiene la cantidad de negras (color existente en su lugar)
	 * @param c Combinacion
	 * @return Cantidad de negras
	 */
	public int getB(char c[]) {
		return c[L+2]-48;
	}
	/**
	 * Fija la distancia entre la combinacion y el codigo
	 * @param i Indice de la combinacion
	 * @param w Distancia entre la combinacion y el codigo
	 */
	public void setFitness(int i, int w) {
		poblacion[i][L+0] = (char)(48+w);
	}
	/**
	 * Fija la cantidad de blancas a una combinacion
	 * @param i Indice de la combinacion
	 * @param w Cantidad de blancas
	 */
	public void setW(int i, int w) {
		poblacion[i][L+1] = (char)(48+w);
	}
	/**
	 * Fija la cantidad de negras a una combinacion
	 * @param i Indice de la combinacion
	 * @param w Cantidad de negras
	 */
	public void setB(int i, int w) {
		poblacion[i][L+2] = (char)(48+w);
	}

	/**
	 * Clona un arreglo de tipo char
	 * @param A Arreglo fuente
	 * @return Clon de A
	 */
	public char[] clone(char[] A) {
		char[] ret =new char[A.length];
		for(int i=0; i<A.length;i++)
			ret[i] = A[i];
		return ret;
	}
	/**
	 * Crea una poblacion entera  
	 * @param cantidad Cantidad de la poblacion
	 */
	public void crearPoblacion(int cantidad) {
		poblacion = new char[cantidad][];
		for(int i=0; i<cantidad; i++) {
			poblacion[i] = crearCombinacionUniq();
		}
		
	}
	/**
	 * Imprime la poblacion
	 *
	 */
	public void imprimirPoblacion() {
		for(int i=0; i<poblacion.length; i++) {
			System.out.println(i+" -> "+String.valueOf(poblacion[i]));
		}
	}
	
	/**
	 * Crea el codigo secreto
	 *
	 */
	public void crearCodigo(){
		codigo = crearCombinacion();
	}
	/**
	 * Obtiene el codigo secreto
	 * @return codigo secreto
	 */
	public char[] getCodigo() {
		return codigo;
	}
	/**
	 * Genera un codigo secreto (manual)
	 * @param nuevoCodigo Codigo secreto
	 */
	public void setCodigo(char[] nuevoCodigo) {
		codigo = nuevoCodigo;
		//System.out.println(historia[0]);
		//D(codigo, 0);		
		//historia[0] = getIndividuo(0);
		//System.out.println(historia[0]);
	}
	/**
	 * Obtiene un individuo de la poblacion
	 * @param i Indice de la poblacion
	 * @return Individuo i
	 */
	public static char[] getIndividuo(int i) {
		return poblacion[i];
	}
	/**
	 * Fija un individuo en la poblacion
	 * @param i Indice de la poblacion
	 * @param nuevoIndividuo Nuevo Individuo para el indice I
	 */
	public void setIndividuo(int i, char[] nuevoIndividuo) {
		poblacion[i] =  nuevoIndividuo;
	}
	
	/**
	 * Agrega una combinacion al historial de jugadas
	 * @param combinacion combinacion a agregar
	 * @return true si aun no se ha llegado al maximo de jugadas, caso contrario false
	 */
	public boolean agregarCombinacionHistoria(char [] combinacion) {
		if(nJ<J) {
			historia[nJ++] = clone(combinacion);
			return true;
		} else
			return false;
			
	}
	/**
	 * Obtiene la ultima combinacion agregada a la historia
	 * @return combinacion
	 */
	public char[] sacarUltimaCombinacionHistoria() {
		return historia[nJ-1];
	}
	/**
	 * Obtiene la historia de jugadas 
	 * @param i Indice de la jugada
	 * @return Combinacion Jugada
	 */
	public char[] getHistoria(int i) {
		return historia[i];
	}
	
	/**
	 * Crea una instancia de MasterMindBase 
	 * @param np # de poblacion
	 * @param nj # maximo de jugadas
	 * @param nh # de generaciones antes de hipermutacion
	 * @param nc % de cruza
	 * @param nt % de transposicion
	 * @param nm % de mutacion circular
	 * @param nr # de hipermutaciones antes de game over
	 */
	public MasterMindBase(int np, int nj, int nh, int nc, int nt, int nm, int nr) {				
		nPob = np;
		J = nj;
		nH = nh;
		nC = nc;
		nT = nt;
		nM = nm;
		nR = nr;
		
		crearCodigo();
		crearPoblacion(nPob);
		historia= new char[J][];
		D(getCodigo(), 0);		
		agregarCombinacionHistoria(getIndividuo(0));		
	}
	
	/**
	 * Crea una instancia de MasterMindBase
	 *
	 */
	public MasterMindBase() {
		crearCodigo();
		crearPoblacion(nPob);
		historia= new char[J][];
		D(getCodigo(), 0);		
		agregarCombinacionHistoria(getIndividuo(0));		
	}
	/**
	 * QuickSort
	 * @param izq izquierda
	 * @param der derecha
	 */
	public void qsm( int izq, int der) {
		int i = izq;
		int j = der;
		int pivote = getFitness( (izq + der) / 2);
		do {
		    while (getFitness(i) < pivote) {
		    	i++;
		    }
		    while (getFitness(j) > pivote) {
		    	j--;
		    }
		    if (i <= j) {
			
				char[] t = getIndividuo(i);			
				setIndividuo(i, getIndividuo(j));
				setIndividuo(j, t);
				
				i++;
				j--;
		    }
		} while (i <= j);
		
		if (izq < j) {
		    qsm(izq, j);
		}
		if (i < der) {
		    qsm(i, der);
		}
    }
	/**
	 * Ordenamiento usando quicksort
	 *
	 */
    public void sort(){
    	qsm(0,nPob-1);
    }
    /**
     * Ordenamiento usando burbuja
     *
     */
    public void sort2() {
    	for(int i = 0; i< nPob-1; i++ ) {
    		for(int j= i+1; j<nPob; j++) {
    			if(getFitness(i)>getFitness(j)) {
    				char[] t = getIndividuo(i);			
    				setIndividuo(i, getIndividuo(j));
    				setIndividuo(j, t);
    			}
    		}
    	}
    }
	
    /**
     * Elimina y cuenta las posiciones repetidas de una combinacion comparada con otra
     * @param A Combinacion a comparar
     * @param B Combinacion Principal
     * @return Combinacion sin colores en comun (en la misma posicion y el mismo color)
     */
    private char[] D2(char[] A, char[] B) {
    	char[] ret = new char[A.length];
    	for(int i=0; i<L; i++) {
    		if(A[i]==B[i]) {
    			ret[i] = ' ';
    			B[L+1]++;
    		} 
    		else
    			ret[i]=A[i];
    	}	    
    	return ret;
    }
    /**
     * Cuenta el numero de colores existenes pero fuera de su posicion
     * @param A Combinacion sin colores en su lugar
     * @param B Combinacion Principal
     */
    private void D3(char[] A, char[] B) {
    	for(int i=0; i<L; i++) {
    		if(A[i]!=' ') {
    			for(int j=0; j<L; j++) {
    				if(B[i]==A[j]) {
    					A[j] = '*';
    					B[L+2]++;
    					break;
    				}
    			}
    		}
    	}    	
    }
	/**
	 * Calcula la cantidad de Blancas y/o Negras entre dos combinaciones
	 * @param pi Combinacion Nueva
	 * @param pj Combinacion de la poblacion
	 */    
	public void D(char[] pi, int pj) {
		setB(pj, 0);
		setW(pj, 0);
		D3(D2(pi, getIndividuo(pj)), getIndividuo(pj));						
	}	
	/**
	 * Imprime la pila de jugadas (historia)
	 *
	 */
	public void impHistoria() {
		for(int i=0; i<nJ; i++)
			System.out.println(i+" -> "+String.valueOf(getHistoria(i)).substring(0,5) );
	}
	/**
	 * Valor absoluto de un numero entero
	 * @param a Numero
	 * @return Absoluto de a
	 */
	private int abs(int a) {
		return a<0?(a*(-1)):a;
	}
	/**
	 * Calcula y fija el fitness (distancia) entre la nueva generacion y la historia
	 * @return True si existe una combinacion que cumpla con la consistencia, en caso contrario false
	 */
	public boolean fitness() {
		int suma;
		boolean ret = false;
		for(int i=0; i<nPob; i++ ) {
			suma =0;
			for(int j=0; j<nJ; j++) {
				D(getHistoria(j), i);
				suma += abs( getW(getHistoria(j)) - getW(getIndividuo(i)) )+
				        abs( getB(getHistoria(j)) - getB(getIndividuo(i)) );
			}
			setFitness(i, suma);
			if(suma==0) ret = true;
		}
		return ret;
	}
	/**
	 * Existe un caracter entre 0 y n de un arreglo 
	 * @param source Arreglo fuente
	 * @param f Caracter buscado
	 * @param n Limite de la busqueda
	 * @return True si existe el caracter en la fuente, en caso contrario false
	 */
	public static boolean existeEn(char[] source, char f, int n) {
		for(int i=0; i<n; i++)
			if(source[i]==f)
				return true;
		return false;
	}

		
	/**
	 * Test de MasterMind
	 * @param args
	 */
	public static void main(String[] args) {
		long t1 = new java.util.Date().getTime();
		long t2 = 0;
		long t3 =0;
		MasterMind g;		
		double n=0;
		double k=0;		
		long mejorTiempo = 0;
		long peorTiempo = 0;
		int peorJugada = 0;
		int mejorJugada=0;
		for(int i=0; i<500; i++) {
			g = new MasterMind(400, 10, 15, 40, 40, 20, 200);
			t2 = new java.util.Date().getTime();
			if(g.jugar()) {
				//System.out.println(i+" Ganaste\n\t" + String.valueOf(g.getCodigo()).substring(0,L) +"\n\t"+String.valueOf(g.getHistoria(g.nJ-1)).substring(0,L));
				n+=g.nJ;
				k++;
				
				if(i==0) {
					mejorJugada= peorJugada= g.nJ;
				}
				else {
					if(mejorJugada>(g.nJ))
						mejorJugada = g.nJ;
					if(peorJugada<(g.nJ))
						peorJugada=g.nJ;
				}
				
			}
			else {
			//	System.out.println(i+" Perdiste");
			}
			t3 = new java.util.Date().getTime();
			if(i==0) {
				mejorTiempo = peorTiempo = t3-t2;
			}
			else {
				if(mejorTiempo>(t3-t2))
					mejorTiempo = t3-t2;
				if(peorTiempo<(t3-t2))
					peorTiempo=t3-t2;
			}
		}		
		System.out.println("Cantidad Ganada   = "+k);
		System.out.println("Promedio de ganar = "+(n/k));						
		System.out.println("\nTiempo transcurrido ="+(new java.util.Date().getTime()-t1) );
		System.out.println("Peor Tiempo\t= "+peorTiempo);
		System.out.println("Mejor Tiempo\t= "+mejorTiempo);
		System.out.println("Peor Jugada\t= "+peorJugada);
		System.out.println("Mejor Jugada\t= "+mejorJugada);
					
	}

}
